import java.util.HashMap;
import java.util.Map;

public class 使数组和能被P整除 {
    public int minSubarray(int[] nums, int p) {
        int sum = 0; // 数组的总和
        int n = nums.length;
        int ans = Integer.MAX_VALUE; // 要求求最短, 所以设成最大值
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1); // 初始化处理
        for (int num : nums) sum = (sum + num) % p; // 求出总和的余数
        // 如果刚好整除直接返回 0
        if (sum == 0) {
            return 0;
        }
        for (int i = 0,x = 0; i < n; i++) {
            x += nums[i]; // 前缀和添加
            x %= p; // 同余操作
            int t = (x - sum + p) % p; // 找出满足前缀和的数组
            if (map.containsKey(t)) {
                // 更新答案
                ans = Math.min(ans,i - map.get(t));
            }
            // 每次都要更新下标
            map.put(x,i);
        }
        // 如果 ans 是要将整个数组全部都清空掉才可以返回的话, 就返回 -1
        return ans == n ? -1 : ans;
    }
}
